package opg2;

import java.util.Iterator;
import java.util.Random;

public class RandomQueue2<Item> implements Iterable<Item> {

	private Item[] a; // stack entries
	private int N;
	private Random r;
	
	public RandomQueue2(int cap) {
		a = (Item[]) new Object[cap];
		r = new Random();
	}

	public boolean isEmpty() {
		return N == 0;
	}

	public int size() {
		return N;
	}

	// push
	public void enqueue(Item item) {
		// add item to top of stack
		if (N == a.length)
			resize(2 * a.length);
		a[N++] = item;
	}

	// pop
	public Item dequeue() {
		// remove from top of stack
		Item item = a[--N];
		a[N] = null; // avoid loitering
		if ((N > 0) && (N == a.length / 4))
			resize(a.length / 2);
		return item;
	}

	private void resize(int max) {
		// / move stack of size N <= max to a new array of size max
		Item[] tmp = (Item[]) new Object[max];
		for (int i = 0; i < N; i++)
			tmp[i] = a[i];
		a = tmp;
	}

	// return but do not remove
	public Item sample() {
		
		if(!isEmpty()) return a[r.nextInt(N)]; 
		else
			return null; // lazy bastard 
				
		/*Iterator<Item> itr = iterator();
		if (itr.hasNext()) {
			return itr.next();
		} else {
			throw new RuntimeException("No items in queue");
		}*/
	}

	// ----------------------------------------------------------------
	public static void shuffleArray(int[] a) {
		int n = a.length;
		Random random = new Random();
		random.nextInt();
		for (int i = 0; i < n; i++) {
			int change = i + random.nextInt(n - i);
			swap(a, i, change);
		}
	}

	private static void swap(int[] a, int i, int change) {
		int helper = a[i];
		a[i] = a[change];
		a[change] = helper;
	}

	// return an iterator over the items in random order
	public Iterator<Item> iterator() {
		return new RandomIterator();
	}

	private class RandomIterator implements Iterator<Item> {
		int[] itemID;
		int actual;

		public RandomIterator() {
			actual = 0;
			itemID = new int[N];
			// initialize array
			for (int i = 0; i < N; i++) {
				itemID[i] = i;
			}
			shuffleArray(itemID);
		}

		public boolean hasNext() {
			return actual < N;
		}

		public void remove() {
			throw new RuntimeException("method not supported");
		}

		public Item next() {
			if (actual < N) {
				return a[itemID[actual++]];
			} else {
				throw new RuntimeException("No more items in queue");
			}
		}
	}

	public static void main(String args[]) {

		// Build a queue containing the Integers 1,2,...,6:
		RandomQueue2<Integer> Q = new RandomQueue2<Integer>(10);
		for (int i = 1; i < 7; ++i)
			Q.enqueue(i); // autoboxing! cool!

		// Print 30 die rolls to standard output
		StdOut.print("Some die rolls: ");
		for (int i = 1; i < 30; ++i)
			StdOut.print(Q.sample() + " ");
		StdOut.println();

		// Let's be more serious: do they really behave like die rolls?
		int[] rolls = new int[10000];
		for (int i = 0; i < 10000; ++i)
			rolls[i] = Q.sample(); // autounboxing! Also cool!
		StdOut.printf("Mean (should be around 3.5): %5.4f\n",
				StdStats.mean(rolls));
		StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
				StdStats.stddev(rolls));

		// Let's look at the iterator. First, we make a queue of colours:

		RandomQueue2<String> C = new RandomQueue2<String>(4);
		C.enqueue("red");
		C.enqueue("blue");
		C.enqueue("green");
		C.enqueue("yellow");

		Iterator<String> I = C.iterator();
		Iterator<String> J = C.iterator();

		StdOut.print("Two colours from first shuffle: ");
		StdOut.print(I.next() + " ");
		StdOut.print(I.next() + " ");

		StdOut.print("\nEntire second shuffle: ");
		while (J.hasNext())
			StdOut.print(J.next() + " ");

		StdOut.print("\nRemaining two colours from first shuffle: ");
		StdOut.print(I.next() + " ");
		StdOut.println(I.next());
	}
}
